Computer graphics systems commonly are used for displaying graphical representations of objects on a two dimensional display screen. Current computer graphics systems can provide highly detailed representations and are used in a variety of applications.
In typical computer graphics systems, an object to be represented on the display screen is broken down into a plurality of graphics primitives. Primitives are basic components of a graphics picture and may include points, lines, vectors and polygons, such as triangles. Typically, a hardware/software scheme is implemented to render, or draw, on the two-dimensional display screen, the graphics primitives that represent the view of one or more objects being represented on the screen.
The primitives that define the three-dimensional object to be rendered are provided from a host computer, which defines each primitive in terms of primitive data. For example, when the primitive is a triangle, the host computer may define the primitive in terms of the x,y,z coordinates of its vertices, as well as the R,G,B (red, green, blue) color values of each vertex. Rendering hardware interpolates the primitive data to compute the display screen pixels that are turned on to represent each primitive, and the R,G,B values for each pixel.
Early graphics systems failed to display images in a sufficiently realistic manner to represent or model complex three-dimensional objects. The images displayed by such systems exhibited extremely smooth surfaces, absent textures, bumps, scratches, shadows and other surface details present in the object being modeled.
As a result, methods were developed to display images with improved surface detail. Texture mapping is one such method that involves mapping a source image, referred to as a texture, onto a surface of a three-dimensional object, and thereafter mapping the textured three-dimensional object to the two-dimensional graphics display screen to display the resulting image. Surface detail attributes that are commonly texture mapped include color, specular reflection, normal perturbation, transparency, shadows, surface irregularities and grading.
Texture mapping involves applying one or more point elements, or texels, of a texture to each point element, or pixel, of the displayed portion of the object to which the texture is being mapped. Texture mapping hardware is conventionally provided with information indicating the manner in which the texels in a texture map correspond to the pixels on the display screen that represent the object. Each texel in a texture map is defined by S and T coordinates which identify its location in the two-dimensional texture map. For each pixel, the corresponding texel or texels that map to the pixel are accessed from the texture map via the S and T coordinates associated with that pixel and are incorporated into the final R,G,B values generated for the pixel to represent the textured object on the display screen.
It should be understood that each pixel in an object primitive may not map in a one-to-one correspondence with a single texel in the texture map for every view of the object. For example, the closer the object is to the view port represented on the display screen, the larger the object will appear. As the object appears larger on the display screen, the representation of the texture becomes more detailed. Thus, when the object consumes a fairly large portion of the display screen, a large number of pixels are used to represent the object on the display screen, and each pixel that represents the object may map in a one-to-one correspondence with a single texel in the texture map, or a single texel may map to multiple pixels. However, when the object takes up a relatively small portion of the display screen, a much smaller number of pixels are used to represent the object, resulting in the texture being represented with less detail, so that each pixel may map to multiple texels. Each pixel may also map to multiple texels when a texture is mapped to a small portion of an object. Resultant texel data is calculated for each pixel that maps to more than one texel and typically represents an average of the texels that map to that pixel.
Texture mapping hardware systems typically include a local memory that stores data representing a texture associated with the object being rendered. As discussed above, a pixel may map to multiple texels. If it were necessary for the texture mapping hardware to read a large number of texels that map to a pixel from the local memory to generate an average value, then a large number of memory reads and the averaging of many texel values would be required, which would be time consuming and would degrade system performance.
To overcome this problem, a scheme has been developed that involves the creation of a series of MIP (multum in parvo, or many things in a small place) maps for each texture, and storing the MIP maps of the texture associated with the object being rendered in the local memory of the texture mapping hardware. A MIP map for a texture includes a base map that corresponds directly to the texture map, as well as a series of filtered maps, wherein each successive map is reduced in size by a factor of two in each of the two texture map dimensions. An illustrative example of a set of MIP maps is shown in FIG. 1. The MIP maps include a base map 2 that is eight-by-eight texels in size, as well as a series of maps 4, 6 and 8 that are respectively four-by-four texels, two-by-two texels, and one texel in size.
The four-by-four map 4 is generated by box filtering (downsampling) the base map 2, such that each texel in the map 4 corresponds to an equally weighted average of four texels in the base map 2. For example, the texel 4a in map 4 equals the average of the texels 2a, 2b, 2c, and 2d in map 2, and texels 4b and 4c in map 4 respectively equal the averages of texels 2e-2h and 2i-2l in map 2. The two-by-two map 6 is similarly generated by box filtering map 4, such that texel 6a in map 6 equals the average of texels 4a-4d in map 4. The single texel in map 8 is generated by averaging the four texels in map 6.
Graphics systems generally download, from the main memory of the host computer to the local memory of the texture mapping hardware, the texture mapping data that is to be used with the primitives to be rendered on the display screen. This procedure may entail downloading the complete series of MIP maps for any texture used with the primitives or merely a portion (i.e., block) of the texture mapping data from a single MIP map. The determination of which MIP map in a series of MIP maps to access to provide the appropriate texel data for a particular pixel is based upon the number of texels to which the pixel maps. For example, if the pixel maps in a one-to-one correspondence with a single texel in the texture map, then the base map 2 is accessed. However, if the pixel maps to four, sixteen, or sixty-four texels, then the maps 4, 6 and 8 are respectively accessed because those maps respectively store texel data representing an average of four, sixteen, and sixty-four texels in the texture map. In order to determine the number of texels to which a pixel maps so that the appropriate MIP map can be accessed, the S and T parameter gradient values (.DELTA.S and .DELTA.T) are calculated. The parameter gradients .DELTA.S, .DELTA.T respectively equal changes in the S and T coordinates between adjacent pixels in both the x and y directions. In essence, the gradients .DELTA.Sx, .DELTA.Sy, .DELTA.Tx and .DELTA.Ty for a display screen pixel indicate the rate of change in coordinate position within the texture map for a change of one pixel on the display screen in the x and y directions in the corresponding S and T dimensions. For example, a gradient equal to two for a display screen pixel indicates that the pixel maps to four texels (i.e., 2.sup.2 texels as discussed below), so that the MIP map that is reduced by two from the base map (e.g., the map 4 in FIG. 1) should be accessed to provide the resultant texture data for the pixel. Thus, as the gradient increases, the size of the MIP map that is accessed to provide the resultant texture data for the pixel reduces in size.
In conventional texture mapping systems, a single gradient is calculated for each pixel, typically equals to the largest of .DELTA.Sx, .DELTA.Sy, .DELTA.Tx, and .DELTA.Ty. However, it should be understood that the gradient for a pixel can be calculated in a variety of well known methods, such as by selecting the smallest of those values or an average of those values. The precise gradient can be calculated by first determining .DELTA.S and .DELTA.T in accordance with equation (1) and (2) below: ##EQU1##
The gradient is thence the greater of .DELTA.S and .DELTA.T. In comparison, by merely taking the maximum of .DELTA.Sx, .DELTA.Sy, .DELTA.Tx, and .DELTA.Ty, the gradient will be in error by .sqroot.2, which is an acceptable margin of error in most cases. Moreover, since a single gradient (e.g., .DELTA.Sx, .DELTA.Sy, .DELTA.Tx or .DELTA.Ty) is selected which only represents the rate of change in one of the S and T coordinates.
Further, a pixel may not map directly to any one texel in the selected map and may fall between two or more texels. In such cases, the values of the S and T coordinates comprise both an integer and fractional portion. Some graphics systems employ bilinear interpolation to accurately produce texel data when this occurs. If a pixel maps into a MIP map between two or more texel entries, then the resulting texel data used is a weighted average of the closest texel entries. Thus, the texel data corresponding to any pixel can be the weighted average of as many as four texel entries in a single map. For example, with reference to FIG. 1, if a pixel maps to a location in map 4 indicated at 4e, the resulting texel data mapping to that pixel would be the weighted average of the texels 4a-4d where the weighted average is dependent upon the fractional portion of the texture coordinates S and T.
Pixels may also not map directly into any one of the maps in the series of MIP maps, and may fall between two maps. For example, a pixel may map to a number of texels in the texture map that is greater than one, but less than four. Some graphics systems address this situation by interpolating between the two closest MIP maps to achieve the resultant texel data. With reference to FIG. 1, an example would be where a pixel maps to greater than one but less than four texels in the texture map. Thus, the texel data provided by maps 2 and 4 would be interpolated to achieve the resultant texel data for the pixel. When combined with the aforementioned interpolation of multiple texel entries in a single map, a scheme known as trilinear interpolation is achieved and can lead to resultant texel data for any one pixel that is generated as a weighted average of as many as eight texels. For instance, the four closest texels in each of the two closest maps are combined as a weighted average of the two maps.
In addition, to display a more accurate and realistic image, perspective correction is often performed on the texture mapping data. A more detailed explanation of perspective correction and the necessity for such can be found, for instance, in J. Blinn, "Hyperbolic Interpolation," IEEE Computer Graphics Applications, pp. 89-94, July 1992.
It has been found that in conventional texture mapping systems which utilize a series of MIP maps of texture data to be mapped onto a displayed image, an amount quantization error occurs when a floating point, or normalized, coordinate system is transformed into a fixed point, or quantized, coordinate system to reduce system bandwidth while maintaining an adequate range of data values. For instance, with reference to FIG. 2, a transformation between a floating point coordinate system having a left edge at 0.0 and a right edge at 1.0, and a quantized coordinate system comprising a four-by-four pixel MIP map having the indicated texel value at the center of each pixel is graphically illustrated. The MIP map shown has a width of four in the S coordinate direction, and length of four in the T coordinate direction. Referring to the top row in the quantized coordinate system, the left edge is actually at (0, -0.5), not 0.0 as in the floating point coordinate system. The same error occurs at right edge which, for the quantized coordinate system, is at (0, 3.5) and not 1.0 as in the floating point space. Thus, coordinate transformation introduces error of 0.5 in the S coordinate values utilized to locate a texel within the MIP map.
Further, it has been found that quantization error also occurs when downsampling MIP maps in order to map more than one texel value to a single display screen pixel. As an example, FIG. 3 provides a one dimensional coordinate system in which a base map of eight texel values is downsampled to four texel values in the base map-1, then to two texel values in the base map-2, and finally to one texel value in the base map-3. The downsampling represented in FIG. 3 is substantially the same as that was performed to produce the series of MIP maps in FIG. 1, as discussed hereinbefore. Using a box filter to downsample from the base map to the base map-1, the 0 texel value and 1 texel value from the base map are blended to create the 0 texel value in the base map-1. Likewise, the 0 texel value and 1 texel value from the base map-1 are blended to create the 0 texel value in the base map-2. Accordingly, the 0 texel value in the base map-2 represents the blended values of the 0, 1, 2, and 3 texel values from the base map.
When a value of 3.5 on the base map is downsampled by dividing by 2 in order to get to the base map-1, the resultant value is 1.75 (i.e., 3.5/2=1.75). Although this seems to result in a correct downsampled value, it is actually incorrect. An error of 0.25 has been introduced in the downsampling process. The value of 3.5 actually corresponds to 1.5 in the base map-1 which represents a constant amount of blend between the texels to the right and the texels to the left of the downsampled value between the two maps. If the downsampling continues without correction to the base map-2, and then to the base map-3, the error is compounded such that, at the base map-3, the value of 3.5 is represented by a value of 0.4375 rather than the correct value of 0. Thus, the resultant values are biased towards the right, and thus, more color is taken from the right side texel values of the base map.
Hence, a heretofore unaddressed need exists in the industry for a texture mapping system that performs texture coordinate alignment in order to correct for quantization error introduced in coordinate system transformation and MIP map downsampling.